﻿(*
  http://projecteuler.net/index.php?section=problems&id=3

  The prime factors of 13195 are 5, 7, 13 and 29.
  What is the largest prime factor of the number 600851475143 ?
*)
#light

let AllPossiblePrimes = seq {
    let AllLongs = Seq.initInfinite (fun x -> int64 x)
    let TimesSixPlusMinus1 x = seq {
        yield 6L * x - 1L
        yield 6L * x + 1L }
    let PossiblePrimes = seq {
        let AllBut1 = Seq.skip 1 AllLongs
        for x in AllBut1 do yield! TimesSixPlusMinus1 x }
    yield 2L
    yield 3L
    yield! PossiblePrimes }

let IsDivisor n p =
    n % p = 0L
    
let smallestDivisor n =
    let divisor = 
        AllPossiblePrimes
        |> Seq.takeWhile (fun x -> x * x <= n)
        |> Seq.tryFind (IsDivisor n)
    match divisor with
    | Some(int64) -> divisor.Value
    | None        -> n

let rec DivideByBiggestPower (n:int64) divisor =
    if n % divisor = 0L then DivideByBiggestPower (n / divisor) divisor
    else n
    
let rec BiggestDivisor n =
    let smallestDiv = smallestDivisor n
    let rest = DivideByBiggestPower n smallestDiv
    if rest = 1L then smallestDiv
    else BiggestDivisor rest

BiggestDivisor 600851475143L
BiggestDivisor 52L